package com.fml.dataStructure.sort;

import com.fml.dataStructure.sort.util.SortUtils;

/**
 * 插入排序
 */
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];//当前待插入的元素
            int j = i - 1;//已排好序部分最后一个索引

            //从后往前开始，将比current大的元素不断向后移，给current准备位置
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;//插入正确位置
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 3, 2, 5, 6, 8, 10, 12, 4, 0, 7};

        insertionSort(arr);
        SortUtils.printArray(arr);
    }
}

